第 370 场力扣周赛

找到冠军 I

如果某一列全为 \(0\)，则该列表示的队伍会成为冠军。

class Solution {
    public int findChampion(int[][] grid) {
        int n = grid.length;
        for (int j = 0; j < n; j++) {
            int cnt = 0;
            for (int i = 0; i < n && cnt == 0; i++) {
                cnt += grid[i][j];
            }
            if (cnt == 0) {
                return j;
            }
        }
        return -1;
    }
}

找到冠军 II

相当于判断入度为 \(0\) 的节点是否只有一个。

class Solution {
    public int findChampion(int n, int[][] edges) {
        int[] in = new int[n];
        for (var e : edges) {
            in[e[1]]++;
        }
        int ans = -1;
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) {
                if (ans == -1) ans = i;
                else return -1;
            }
        }
        return ans;
    }
}

在树上执行操作以后得到的最大分数

树形 DP，要求最大分数，可以先求损失的最小分数，然后使用总分减去该分数即可。

class Solution {
    public long maximumScoreAfterOperations(int[][] edges, int[] values) {
        int n = values.length;
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (var e : edges) {
            int u = e[0], v = e[1];
            g[u].add(v);
            g[v].add(u);
        }
        long ans = 0L;
        for (int x : values) {
            ans += x;
        }
        return ans - dfs(0, -1, g, values);
    }
    
    private long dfs(int x, int fa, List<Integer>[] g, int[] values) {
        if (g[x].size() == 1 && g[x].get(0) == fa) {
            return values[x];
        }
        long res = 0L;
        for (int y : g[x]) {
            if (y != fa) {
                res += dfs(y, x, g, values);
            }
        }
        return Math.min(res, values[x]);
    }
}

也可以直接正向做，对于每个节点有两种情况：选择当前节点，要求该节点的每个子树都是健康的；不选当前节点，该节点的所有子节点都可以选。

class Solution {
    public long maximumScoreAfterOperations(int[][] edges, int[] values) {
        int n = values.length;
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (var e : edges) {
            int u = e[0], v = e[1];
            g[u].add(v);
            g[v].add(u);
        }
        long[] sum = new long[n];
        return dfs(0, -1, g, values, sum);
    }
    
    private long dfs(int x, int fa, List<Integer>[] g, int[] values, long[] sum) {
        sum[x] = values[x];
        if (g[x].size() == 1 && g[x].get(0) == fa) {
            return 0;
        }
        long dp0 = values[x], dp1 = 0;
        for (int y : g[x]) {
            if (y != fa) {
                dp0 += dfs(y, x, g, values, sum);
                dp1 += sum[y];
            }
        }
        sum[x] += dp1;
        return Math.max(dp0, dp1);
    }
}

平衡子序列的最大和

离散化 + 树状数组优化 DP，直接看灵神代码吧。

// 作者：灵茶山艾府
// 链接：https://leetcode.cn/problems/maximum-balanced-subsequence-sum/solutions/2513121/shu-zhuang-shu-zu-you-hua-dp-by-endlessc-3zf4/
class Solution {
    public long maxBalancedSubsequenceSum(int[] nums) {
        int n = nums.length;
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = nums[i] - i;
        }
        Arrays.sort(b);
 
        BIT t = new BIT(b.length + 1);
        for (int i = 0; i < n; i++) {
            // j 为 nums[i]-i 离散化后的值（从 1 开始）
            int j = Arrays.binarySearch(b, nums[i] - i) + 1;
            long f = Math.max(t.preMax(j), 0) + nums[i];
            t.update(j, f);
        }
        return t.preMax(b.length);
    }
}

// 树状数组模板（维护前缀最大值）
class BIT {
    private long[] tree;

    public BIT(int n) {
        tree = new long[n];
        Arrays.fill(tree, Long.MIN_VALUE);
    }

    public void update(int i, long val) {
        while (i < tree.length) {
            tree[i] = Math.max(tree[i], val);
            i += i & -i;
        }
    }

    public long preMax(int i) {
        long res = Long.MIN_VALUE;
        while (i > 0) {
            res = Math.max(res, tree[i]);
            i &= i - 1;
        }
        return res;
    }
}